1. Field of the Invention
The present invention is directed to systems and methods for implementing error diffusion when processing an image, such as for printing.
2. Description of the Related Art
When printing an image using an output device which places discreet units of colorants (ink drops, toner, etc.) on media, it is necessary to reduce the range of the image pixels to match the reproduction capabilities of the printing device. This typically means a reduction in the bit resolution of the image.
Most often, the reduction in bit resolution is accomplished by halftone transformation. Halftone transformation results, on a pixel-by-pixel basis for all image pixels, in the replacement of an original non-binary, or “gray-level” value of, e.g., 8 bits, with a binary value after comparison with some threshold. The threshold itself may vary dynamically depending on the non-binary pixel value, and other factors. The original 8-bit value at each pixel is thus substituted by either a “0” (representing an 8-bit value of 0) or a “1” (representing an 8-bit value of 255). The consequence of such a transformation at a pixel is that the overall “brightness” of the image is changed. To mitigate this, the change, or “error”, may be diffused to nearby, as yet untransformed pixels through a technique known as error diffusion. Error diffusion works by spreading the inaccuracy, or error, of the halftone decision at one pixel in the output image among nearby pixels, creating a visually superior transformation. Each original pixel value is adjusted based on the error contributed by adjacent and nearby pixels, and these contributions are taken into account in calculating the correct transformed value for the pixel.
There are a number of error diffusion techniques, each of which uses a different combination of thresholding approaches, collection of nearby pixels to which the error is spread, error weightings to each of these nearby pixels, and other factors. The Floyd-Steinberg algorithm, developed in 1975 and known to those skilled in the art, is one of the more well-known implementations of error diffusion. This algorithm generates a series of error values for each image element as an image line is transformed. These error values are calculated by taking a fraction of nearby pixel error values and adding them together to represent a pixel location.
In the Floyd-Steinberg algorithm, the error at a transformed pixel 420 is spread to a collection of four specific nearby pixels in the fashion shown in FIG. 4A. The error from a just-transformed pixel 420 is spread to pixels 422, 424, 426 and 428 using error spread weights 7/16, 1/16, 5/16 and 3/16, respectively, the error spread weights representing the proportion of error at transformed pixel 420 that is spread to each adjacent untransformed, error-receiving pixel. Thus, from the perspective of a just-transformed pixel 420, its total error is spread to “Next Back” pixel 428 (with “send backward coefficient” 3/16), “Next Below” pixel 426 (with “send below coefficient” 5/16), “Next Forward” pixel 424 (with “send forward coefficient” 1/16), and “Current Right” pixel 422 (with “send right coefficient” 7/16). In the foregoing nomenclature, the prefix “Next” refers to the next line to which the corresponding errors are spread.
FIG. 4B shows receipt of partial errors from the perspective of a pixel 450 that is about to be transformed using Floyd-Steinberg error diffusion. Soon-to-be transformed pixel 450 receives a portion of the error from each of four nearby, previously transformed pixels 452, 454, 456 and 458, using error spread weights of 7/16, 1/16, 5/16 and 3/16, respectively. Of these, pixels 454, 456 and 458 are on the previous line (“above”), while recently-transformed pixel 452 is immediately to the left of untransformed pixel 450, on the current line. From the perspective of untransformed pixel 450, error is received from “Previous Back” pixel 454 (with “receive backward coefficient” 1/16), “Previous Above” pixel 456 (with “receive above coefficient” 5/16), “Previous Forward” pixel 458 (with “receive forward coefficient” 3/16), and “Current Left” pixel 452 (with “receive left coefficient” 7/16). In the foregoing nomenclature, the prefix “Previous” refers to the previous line from which the corresponding errors are received.
From the foregoing description, it can be seen that in the Floyd-Steinberg algorithm the error created from transforming a pixel is spread to four adjacent pixels. Furthermore, prior to transformation, each pixel receives a portion of the error from each of the four adjacent pixels that have previously been transformed.
The Floyd-Steinberg algorithm typically operates in row order (sometimes called “line order”). That is, an entire row, or line, of an image is transformed before the next row or line is transformed. Transformation of a row results in the storage of a large number of error values. For instance, if an image has a resolution of 600 pixels per inch (PPI), and each row of the image is 9 inches wide, then 5400 pixels worth of error data, each error datum comprising anywhere from 1 color (for a black & white printer) to 3 or more colors (for a color printer), may need to be stored.
Originally, the Floyd-Steinberg algorithm was implemented in software with data being read from, and written to a main memory having ample space. More recently, however, high-speed ASIC-based hardware implementations using integer arithmetic have been realized. For cost reasons, it is best to minimize the amount of memory used in such implementations.